One major use of the Border Gateway Protocol (BGP) protocol is to establish connections between inter-connected different autonomous systems (ASs) to exchange routing information. When a BGP speaker receives routes from a peer in a different autonomous system over an external BGP connection, the BGP speaker will generally redistribute the received routes to all its internal BGP peers in the same AS over internal BGP connections, or redistribute the received routes to an internal BGP peer which acts as Route Reflector (RR). When the external BGP peer is shut down, the BGP peer needs to withdraw all the previously redistributed routes from its internal BGP peers. The route withdrawal is performed by the following two steps in sequence: (1) the BGP speaker encodes all the withdrawn routes in the UPDATE messages, and then sends them to all other internal BGP peers; and (2) all the other internal BGP peer decodes all the withdrawn routes, and then removes the routes one-by-one from their BGP routing table. In a BGP core router, there may be hundreds of thousands of routes to be withdrawn, and thus the UPDATE message may contain hundreds of thousands of withdrawn routes, which will require much processing in encoding, decoding, and processing of the withdrawn routes.
Another major use of the BGP protocol is to redistribute and exchange multiprotocol routing information by its multiprotocol extensions. In particular, the BGP multiprotocol extension can be used to exchange IPv4 virtual private network (VPN) routing information among different sites. When a provider edge (PE) router receives routes from a CE (CE) router over its attachment circuit, the PE router needs to redistribute to other PE routers which connect to other CE routers for the same customer VPN. When such a CE router is shut down, the corresponding PE router needs to withdraw the previously announced routes from all other PE routers which serve the same VPN. All the withdrawn routes need to be encoded in the UPDATE message by the sender, then decoded and processed in the UPDATE message by the receiver.